// ParseStrokeKeyPoint.cpp: implementation of the CParseStrokeKeyPoint class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Point.h"
#include "ParseStrokeKeyPoint.h"
#include "ContourDistance.h"
#include <math.h>
#include "AutoFiller.h"
#include <memory.h>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

/// for '乃', should be at least 6
const int M = 7;
/// for simpler coding, to use stack space, at least (M+2)
const int MAX_COUNT = 10;
/// for temporary buffer
const int MAX_ARRAY = (MAX_COUNT + 1) * MAX_COUNT / 2;
/// to prevent from float error
const float EPSILON = 1.0e-5f;
/// to denote unexpected error
const float MAX_FLOAT = 1.0e+6f;

#ifndef _countof
#define _countof(A) (sizeof(A)/sizeof(A[0]))
#endif	// _countof

int getMinIndex(const float *pfData, int nSize, float fEpsilon);
int getMaxIndex(const float *pfData, int nSize, float fEpsilon);

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CParseStrokeKeyPoint::CParseStrokeKeyPoint()
{
	// shade area is a bad algorithm, test case: '隧'-13th
	m_nDistanceMethod = 0;
	// too slow to run, for research only
	m_bEnableExhaust = FALSE;
	// to use accelerating method or not
	m_bFastAlgorithm = TRUE;

	m_lpPoint = NULL;
	m_nPoint = 0;
	m_maxSize.cx = 0;
	m_maxSize.cy = 0;

	m_ptCheck = NULL;
	m_nBackup = 0;
	m_ptCache = NULL;

	m_pbNear = NULL;
	m_pCheck = NULL;
}

CParseStrokeKeyPoint::~CParseStrokeKeyPoint()
{
	Destruct();
}

BOOL CParseStrokeKeyPoint::setAllPoint(const SPoint *lpPoint, int nPoint, const SIZE *lpSize)
{
	if (!lpPoint || nPoint<2 || !lpSize ||
		lpSize->cx<=0 || lpSize->cy<=0 ||
		lpSize->cx>=65536 || lpSize->cy>=65536)
		return FALSE;
	if (m_ptCheck != NULL)
	{
		delete[] m_ptCheck;
		m_ptCheck = NULL;
	}
	m_nBackup = 0;
	// internal code use short, so, no more than 65535
	m_lpPoint = lpPoint;
	m_nPoint = nPoint;
	if (m_ptCache!=NULL && (m_maxSize.cx<lpSize->cx || m_maxSize.cy<lpSize->cy))
	{
		delete[] m_ptCache;
		m_ptCache = NULL;
	}
	m_maxSize = *lpSize;
	if (m_ptCache == NULL && m_nDistanceMethod >= 4)
	{
		int nMaxCache = (m_maxSize.cx + m_maxSize.cy + 1) * 5;
		m_ptCache = new SFPoint[nMaxCache * 2];
	}
	return TRUE;
}

int CParseStrokeKeyPoint::createPointList(SPoint *ptOut, int nOut)
{
	ASSERT(this != NULL);
	if (!ptOut || nOut < 2)
		return 0;
	if (m_nPoint <= nOut) {
		memcpy(ptOut, m_lpPoint, sizeof(SPoint)*m_nPoint);
		return m_nPoint;
	}
	for(int i=0; i<nOut; i++) {
		ptOut[i].x = (short)-1;
		ptOut[i].y = (short)-1;
	}
	RECT rect;
	findPointRect(&rect, TRUE);
	SFindPointContext context;
	context.rectMax = rect;
	context.ptKey = NULL;
	context.m_fError = 0;
	findPoint(ptOut, nOut, &context);
	return nOut;
}

int CParseStrokeKeyPoint::createBestPointList(SPoint *ptOut, int nOut, BOOL *pfStop)
{
	ASSERT(this != NULL);
	if (!ptOut || nOut < 6)
		return 0;
	if (m_ptCheck != NULL)
	{
		delete[] m_ptCheck;
		m_ptCheck = NULL;
	}
	m_nBackup = 0;
	memset(m_CntList, 0, sizeof(int)*MAX_OUT);
	if (!m_lpPoint || m_nPoint<=1)
		return 0;
	if (m_nPoint == 2)
	{
		memcpy(ptOut, m_lpPoint, sizeof(SPoint)*m_nPoint);
		return m_nPoint;
	}
	ASSERT(M+2 <= MAX_COUNT);
	float fError[MAX_COUNT];
	// to back up other points
	if (m_ptCheck == NULL)
		m_ptCheck = new SPoint[MAX_ARRAY];
	if (!createPointListError(fError, 2, M+1, pfStop))
		return 0;
	// to output
	RECT rect;
	findPointRect(&rect, FALSE);
	int m = selectBestIndex(fError, &rect);
	if (m < 0)
		return -1;
	// to adjust for neighbour points case, horizontal stroke only
	if (m>2 && checkNeighbourPoint(m_ptCheck+m_BaseList[m], m) && checkRegionSharp(&rect))
	{
		do{
			m--;
		}while(m>2 && checkNeighbourPoint(m_ptCheck+m_BaseList[m], m));
	}
	memcpy(ptOut, m_ptCheck+m_BaseList[m], sizeof(SPoint)*m);
	m_nBackup = MAX_ARRAY;
	return m;
}

int CParseStrokeKeyPoint::getBackupPoint(SPoint *ptOut, int nOut) const
{
	ASSERT(this != NULL);
	if (!ptOut || nOut<1 || nOut>m_nPoint || nOut>MAX_OUT)
		return -1;
	if (m_nPoint == 2)
	{
		if (nOut != 2)
			return 0;
		memcpy(ptOut, m_lpPoint, sizeof(SPoint)*2);
		return 2;
	}
	int n = m_CntList[nOut];
	if (!m_ptCheck || n<=0 || m_nBackup<=0)
		return 0;
	memcpy(ptOut, m_ptCheck+m_BaseList[nOut], sizeof(SPoint)*n);
	return n;
}

BOOL CParseStrokeKeyPoint::Destruct(void)
{
	ASSERT(this != NULL);
	if (m_ptCheck != NULL)
	{
		delete[] m_ptCheck;
		m_ptCheck = NULL;
	}
	m_nBackup = 0;
	if (m_ptCache != NULL)
	{
		delete[] m_ptCache;
		m_ptCache = NULL;
	}
	if (m_pbNear != NULL)
	{
		delete[] m_pbNear;
		m_pbNear = NULL;
	}
	return TRUE;
}

BOOL CParseStrokeKeyPoint::enableCheckInContour(CCheckInContour *pCheck)
{
	ASSERT(this != NULL);
	m_pCheck = pCheck;
	return TRUE;
}

///////////////////////////////////////////////////////////////////////////////

BOOL CParseStrokeKeyPoint::createPointListError(float *fError, int nMinCount, int nMaxCount, BOOL *pfStop)
{
	RECT rect;
	findPointRect(&rect, TRUE);
	SFindPointContext context;
	context.rectMax = rect;
	context.ptKey = NULL;
	context.m_fError = 0;
	int nBase = 0;
	int nRatio = 1;
	if (m_nDistanceMethod==6 && !enableCheckNearMiddleLine())
		return FALSE;
	SPoint *ptBuf = NULL;
	CParseStrokeKeyPoint *pParser = NULL;
	for(int i=nMinCount; i<=nMaxCount; i++)
	{
		if (pfStop && *pfStop)
			return FALSE;
		m_BaseList[i] = nBase;
		if (i < m_nPoint) {
			if (m_bFastAlgorithm && (rect.right-rect.left+1>=32 || rect.bottom-rect.top+1>=32)) {
				if (pParser == NULL) {
					pParser = new CParseStrokeKeyPoint();
					SIZE maxSize = {16, 16};
					nRatio = (max(rect.right-rect.left+1, rect.bottom-rect.top+1) + 16 - 1) / 16;
					ptBuf = new SPoint[m_nPoint];
					int nBuf = 0;
					for(int n=0; n<m_nPoint; n++) {
						ptBuf[nBuf].x = (short)((m_lpPoint[n].x - rect.left) / nRatio);
						ptBuf[nBuf].y = (short)((m_lpPoint[n].y - rect.top) / nRatio);
						if (nBuf>0 && ptBuf[nBuf].x==ptBuf[nBuf-1].x && ptBuf[nBuf].y==ptBuf[nBuf-1].y)
							NULL;
						else
							nBuf++;
					}
					pParser->setAllPoint(ptBuf, nBuf, &maxSize);
				}
				SPoint ptOut[MAX_OUT];
				pParser->createPointList(ptOut, i);
				for(int n=0; n<i; n++) {
					ptOut[n].x = (short)(ptOut[n].x * nRatio + rect.left);
					ptOut[n].y = (short)(ptOut[n].y * nRatio + rect.top);
				}
				fError[i] = getDistanceFromInitialPoint(ptOut, i, &rect);
				memcpy(m_ptCheck+nBase, ptOut, sizeof(SPoint)*i);
			} else {
				if (i > 2) {
					context.m_fError = fError[i-1];
					context.ptKey = m_ptCheck + m_BaseList[i-1];
				}
				fError[i] = findPoint(m_ptCheck+nBase, i, &context);
			}
			m_CntList[i] = i;
			nBase += i;
		} else {
			// test case: ∞¶, 7th
			fError[i] = 0;
			memcpy(m_ptCheck+nBase, m_lpPoint, sizeof(SPoint)*m_nPoint);
			m_CntList[i] = m_nPoint;
			nBase += m_nPoint;
		}
	}
	if (ptBuf != NULL)
		delete[] ptBuf;
	if (pParser != NULL)
		delete pParser;
	if (pfStop && *pfStop)
		return FALSE;
	// to set default value
	m_BaseList[1] = nBase;
	m_CntList[1] = 1;
	fError[1] = findCentralPoint(m_ptCheck+nBase, &rect);
	fError[0] = fError[1] + 1000;
	return TRUE;
}

int CParseStrokeKeyPoint::selectBestIndex(const float *fError, const RECT *lpRect) const
{
	int nMax = max(lpRect->right-lpRect->left+1, lpRect->bottom-lpRect->top+1);
	float mCheck = nMax / 10.0f;
	// case(m < M): only 2 or 3 points is enough
	int i, m = getMinIndex(fError+2, M-1, EPSILON) + 2;
	if (m >= M)
	{
		// to find the best change point
		float fDelta1[MAX_COUNT];
		// order-1 derivation
		for(i=1; i<=M; i++)
			fDelta1[i] = fError[i] - fError[i+1];
		fDelta1[0] = 0;
		// order-2 derivation
		// k = |d2| / (1 + d1^2)^(3/2)
		float fDelta2, fKappa[MAX_COUNT];
		for(i=2; i<=M; i++)
		{
			fDelta2 = fabsf(fDelta1[i] - fDelta1[i-1]);
			fKappa[i] = fDelta2 / (float)exp(1.5f * log(1.0f + fDelta1[i] * fDelta1[i]));
		}
		// not to check index-0,1, at most (M-1) value(in [2, M])
		m = getMaxIndex(fKappa+2, M-1, EPSILON) + 2;
	}
	// need to select a large m to keep detail?
	if (m<M && fError[m]>mCheck && fError[m+1]<fError[m]*0.5f)
		m++;
	// if it is small enough, stop;
	// test case: 猁, 5th; 矗, 24th; 隧, 13th; 腓, 11th; 棚, 11th; 掐, 8th; 辄, 8th
	float fSmall = max(mCheck*0.5f, 1);
	for(i=2; i<m; i++)
	{
		if (fError[i]<fSmall || (fError[i]<mCheck && fError[i+1]>fError[i]*0.8f))
		{
			m = i;
			break;
		}
	}
	return m;
}

void CParseStrokeKeyPoint::findPointRect(RECT *lpRect, BOOL bEnlarge) const
{
	RECT rect = {m_lpPoint[0].x, m_lpPoint[0].y, m_lpPoint[0].x, m_lpPoint[0].y};
	for(int i=1; i<m_nPoint; i++)
	{
		rect.left = min(rect.left, m_lpPoint[i].x);
		rect.top = min(rect.top, m_lpPoint[i].y);
		rect.right = max(rect.right, m_lpPoint[i].x);
		rect.bottom = max(rect.bottom, m_lpPoint[i].y);
	}
	if (bEnlarge)
	{
		int n = max(m_maxSize.cx, m_maxSize.cy) / 16;
		n = min(n, 5);
		lpRect->left = max(rect.left - n, 0);
		lpRect->top = max(rect.top - n, 0);
		lpRect->right = min(rect.right + n, m_maxSize.cx - 1);
		lpRect->bottom = min(rect.bottom + n, m_maxSize.cy - 1);
	}
	else
	{
		lpRect->left = max(rect.left, 0);
		lpRect->top = max(rect.top, 0);
		lpRect->right = min(rect.right, m_maxSize.cx - 1);
		lpRect->bottom = min(rect.bottom, m_maxSize.cy - 1);
	}
}

int CParseStrokeKeyPoint::enumRectPoint(SPoint **ppPoint, const RECT *lpRect) const
{
	// to set default NULL output
	*ppPoint = NULL;
	int nW = lpRect->right - lpRect->left + 1;
	int nH = lpRect->bottom - lpRect->top + 1;
	int nMax = nW * nH;
	// to enumerate all points
	int nOut = 0;
	SPoint *pt = new SPoint[nMax];
	for(int y=lpRect->top; y<=lpRect->bottom; y++)
	{
		//int n;
		//int nBase = (y - lpRect->top) * nW;
		for(int x=lpRect->left; x<=lpRect->right; x++)
		{
			//n = nBase + x - lpRect->left;
			pt[nOut].x = (short)x;
			pt[nOut].y = (short)y;
			if (checkDistLessEqual(&pt[nOut], 5))
				nOut++;
		}
	}
	// to output
	*ppPoint = pt;
	return nOut;
}

BOOL CParseStrokeKeyPoint::checkDistLessEqual(const SPoint *lpPoint, int nDist) const
{
	int x = lpPoint->x;
	int y = lpPoint->y;
	for(int i=1; i<m_nPoint; i++)
	{
		SPoint pt0 = m_lpPoint[0];
		SPoint pt1 = m_lpPoint[1];
		if (pt0.x==pt1.x && pt0.y==pt1.y)
			continue;
		if ((abs(pt0.x-x) <= nDist && abs(pt0.y-y)<=y) ||
			(abs(pt1.x-x) <= nDist && abs(pt1.y-y)<=y))
			return TRUE;
		int dx = pt1.x - pt0.x;
		int dy = pt1.y - pt0.y;
		float fMax = sqrtf(dx * dx + dy * dy + 0.0f);
		float f = (y * dx - x * dy) / fMax;
		if (f <= nDist)
			return TRUE;
	}
	return FALSE;
}

BOOL CParseStrokeKeyPoint::checkRegionSharp(const RECT *lpRect) const
{
	int nMaxX = lpRect->right - lpRect->left + 1;
	int nMaxY = lpRect->bottom - lpRect->top + 1;
	if ((nMaxX>=12 && nMaxX>=6*nMaxY) ||
		(nMaxY>=12 && nMaxY>=6*nMaxX))
		return TRUE;
	int dx = m_lpPoint[m_nPoint-1].x - m_lpPoint[0].x;
	int dy = m_lpPoint[m_nPoint-1].y - m_lpPoint[0].y;
	float fBase = sqrtf((float)dx * dx + dy * dy);
	if (fBase < EPSILON)
		return FALSE;
	float fx = dx / fBase;
	float fy = dy / fBase;
	float f1, f2, fMinProj, fMaxProj, fMin, fMax;
	f1 = -fy * m_lpPoint[0].x + fx * m_lpPoint[0].y;
	fMinProj = fMaxProj = f1;
	f2 = fx * m_lpPoint[0].x + fy * m_lpPoint[0].y;
	fMin = fMax = f2;
	for(int i=1; i<m_nPoint; i++)
	{
		f1 = -fy * m_lpPoint[i].x + fx * m_lpPoint[i].y;
		fMinProj = min(fMinProj, f1);
		fMaxProj = max(fMaxProj, f1);
		f2 = fx * m_lpPoint[i].x + fy * m_lpPoint[i].y;
		fMin = min(fMin, f2);
		fMax = max(fMax, f2);
	}
	float fProjWidth = fMaxProj - fMinProj;
	float fWidth = fMax - fMin;
	if (fWidth>=12 && fWidth>=6*fProjWidth)
		return TRUE;
	return FALSE;
}

/////////////////////////////////////////////////////////////////////////////

/// for exhausted searching
struct SLargeIndex
{
public:
	/// for large index number
	int	m_nIndex[MAX_OUT];
	/// count of m_pnIndex;
	int	m_nCount;
	/// excluded, 0-based, should be 2 at least
	int	m_nMaxValue;

public:
	void Init(int nMaxCount, int nMaxValue);
	BOOL updateIndex(void);
	BOOL selectIndex0(void);
	BOOL checkIndex(void) const;
};

void SLargeIndex::Init(int nMaxCount, int nMaxValue)
{
	m_nCount = nMaxCount;
	m_nMaxValue = nMaxValue;
	for(int i=0; i<m_nCount; i++)
		m_nIndex[i] = i;
}

BOOL SLargeIndex::updateIndex(void)
{
	ASSERT(m_nCount > 0);
	for(int m=m_nCount-1; m>=0; m--)
	{
		m_nIndex[m]++;
		// too large, set former index
		int n = m_nIndex[m];
		if (n >= m_nMaxValue)
		{
			m_nIndex[m] = 0;
			continue;
		}
		// try to check index
		if (checkIndex())
			return TRUE;
		// to update index again
		m = m_nCount;
	}
	// fail
	return FALSE;
}

BOOL SLargeIndex::selectIndex0(void)
{
	for(int i=1; i<m_nCount; i++)
	{
		if ((m_nIndex[i] = m_nIndex[0] + i) >= m_nMaxValue)
			return FALSE;
	}
	return TRUE;
}

BOOL SLargeIndex::checkIndex(void) const
{
	BOOL bSucc = TRUE;
	for(int i=0; bSucc && i<m_nCount; i++)
	{
		for(int j=i+1; bSucc && j<m_nCount; j++)
			bSucc = (m_nIndex[i] != m_nIndex[j]);
	}
	return bSucc;
}

/////////////////////////////////////////////////////////////////////////////

/// for all possible 8 neighbour points
const POINT OFFSET_XY[] = {
	{-1, -1},
	{0, -1},
	{1, -1},
	{-1, 0},
	{1, 0},
	{-1, 1},
	{0, 1},
	{1, 1},
};
BOOL CParseStrokeKeyPoint::offsetPoint(SPoint *lpPoint, int nIndex, const RECT *lpRect) const
{
	ASSERT(0<=nIndex && nIndex<_countof(OFFSET_XY));
	ASSERT(lpPoint!=NULL);
	int x = lpPoint->x + OFFSET_XY[nIndex].x;
	int y = lpPoint->y + OFFSET_XY[nIndex].y;
	// note: left, top, right, bottom are included in rect; see, findPointRect
	if (x < lpRect->left || y < lpRect->top ||
		x > lpRect->right || y > lpRect->bottom)
		return FALSE;
	if (m_nDistanceMethod == 6) {
		if (!checkNearMiddleLine(x, y))
			return FALSE;
	}
	lpPoint->x = (short)x;
	lpPoint->y = (short)y;
	return TRUE;
}

BOOL CParseStrokeKeyPoint::checkNearMiddleLine(int x, int y) const
{
	int nMaxX = (m_maxSize.cx + 7) / 8;
	if (!m_pbNear)
		return FALSE;
	if (m_pCheck!=NULL && !m_pCheck->inContour(x, y))
		return FALSE;
	return ( m_pbNear[y * nMaxX + (x >> 3)] & ( 1 << (x & 7) ) ) != 0;
}

BOOL CParseStrokeKeyPoint::enableCheckNearMiddleLine(void)
{
	int nMaxX = (m_maxSize.cx + 7) / 8;
	if (m_pbNear != NULL) {
		delete[] m_pbNear;
		m_pbNear = NULL;
	}
	if ((m_pbNear=new BYTE[nMaxX * m_maxSize.cy]) == NULL)
		return FALSE;
	memset(m_pbNear, 0, nMaxX * m_maxSize.cy);
	int x, y, dx, dy;
	// to set flag for the first point
	x = m_lpPoint[0].x;
	y = m_lpPoint[0].y;
	m_pbNear[y * nMaxX + (x >> 3)] |= ( 1 << (x & 7) );
	for(int i=1; i<m_nPoint; i++) {
		dx = m_lpPoint[i].x - m_lpPoint[i-1].x;
		dy = m_lpPoint[i].y - m_lpPoint[i-1].y;
		int tMax = max(abs(dx), abs(dy));
		for(int t=0; t<=tMax; t++) {
			// to set for all point
			x = m_lpPoint[i-1].x + dx * t / tMax;
			y = m_lpPoint[i-1].y + dy * t / tMax;
			m_pbNear[y * nMaxX + (x >> 3)] |= ( 1 << (x & 7) );
			// to set flag for neighbor points
			int x0 = x;
			int y0 = y;
			for(int s=0; s<8; s++) {
				x = x0 + OFFSET_XY[s].x;
				y = y0 + OFFSET_XY[s].y;
				if (x<0 || x>=m_maxSize.cx || y<0 || y>=m_maxSize.cy)
					continue;
				m_pbNear[y * nMaxX + (x >> 3)] |= ( 1 << (x & 7) );
			}
		}
	}
	return TRUE;
}

BOOL CParseStrokeKeyPoint::checkNeighbourPoint(const SPoint *lpPoint, int nPoint)
{
	int dx, dy;
	for(int i=1; i<nPoint; i++)
	{
		if ((dx = abs(lpPoint[i].x - lpPoint[i-1].x)) <= 1 &&
			(dy = abs(lpPoint[i].y - lpPoint[i-1].y)) <= 1)
			return TRUE;
	}
	return FALSE;
}

/////////////////////////////////////////////////////////////////////////////

int CParseStrokeKeyPoint::getDistanceType(void) const
{
	ASSERT(this != NULL);
	int n = m_nDistanceMethod;
	if (n <= 0 || n > 5)
		n = 2;
	return n;
}

BOOL CParseStrokeKeyPoint::selectInitialPoint(SPoint *ptInitial, int nSelect, BOOL bDistance) const
{
	if (!ptInitial || nSelect<2)
		return FALSE;
	ptInitial[0] = m_lpPoint[0];
	ptInitial[nSelect-1] = m_lpPoint[m_nPoint-1];
	// will lead to bad intial value; test case: 邈, 16th
	int m, n;
	int nStep = (m_nPoint - 2) / (nSelect - 1);
	nStep = max(nStep, 1);
	for(m=1; m+1<nSelect; m++)
		ptInitial[m] = m_lpPoint[m * nStep];
	// to adjust initial point by length
	if (bDistance && nSelect>2)
	{
		int x, y, dist;
		int nSum = 0;
		for(n=0; n+1<m_nPoint; n++)
		{
			x = m_lpPoint[n+1].x - m_lpPoint[n].x;
			y = m_lpPoint[n+1].y - m_lpPoint[n].y;
			dist = max(abs(x), abs(y));
			nSum += dist;
		}
		int nDistStep = nSum / (nSelect - 1);
		nDistStep = max(nDistStep, 1);
		int nSaveDist;
		m = 1;
		int nCurDist = 0;
		for(n=0; n+1<m_nPoint && m+1<nSelect; n++)
		{
			nSaveDist = nCurDist;
			x = m_lpPoint[n+1].x - m_lpPoint[n].x;
			y = m_lpPoint[n+1].y - m_lpPoint[n].y;
			dist = max(abs(x), abs(y));
			nCurDist += dist;
			if (nCurDist >= m * nDistStep)
			{
				int delta = m * nDistStep - nSaveDist;
				ptInitial[m].x = (short)(m_lpPoint[n].x + delta * x / dist);
				ptInitial[m].y = (short)(m_lpPoint[n].y + delta * y / dist);
				m++;
				n--;
				nCurDist = nSaveDist;
			}
		}
	}
	return TRUE;
}

float CParseStrokeKeyPoint::findPoint(SPoint *ptOut, int nOut, const SFindPointContext *lpContext) const
{
	ASSERT(2<=nOut && nOut<=MAX_COUNT);
	if (m_nPoint <= nOut)
	{
		memcpy(ptOut, m_lpPoint, sizeof(SPoint)*m_nPoint);
		return 0.0f;
	}
	// to select a base solution
	SPoint ptBest1[MAX_COUNT] = {{0, 0}};
	selectInitialPoint(ptBest1, nOut, FALSE);
	float fError1 = getDistanceFromInitialPoint(ptBest1, nOut, &lpContext->rectMax);
	// to select another solution
	SPoint ptBest2[MAX_COUNT] = {{0, 0}};
	selectInitialPoint(ptBest2, nOut, TRUE);
	float fError2 = getDistanceFromInitialPoint(ptBest2, nOut, &lpContext->rectMax);
	if (fError2 < fError1 - EPSILON)
		memcpy(ptOut, ptBest2, sizeof(SPoint)*nOut);
	else
		memcpy(ptOut, ptBest1, sizeof(SPoint)*nOut);
	float fError = min(fError1, fError2);
	// still too large, to use another search way
	if (lpContext->ptKey!=NULL && fError>lpContext->m_fError+EPSILON)
	{
		int i, j, nMax = nOut - 2;
		for(i=0; i<nMax; i++)
		{
			for(j=0; j<=i; j++)
				ptBest1[j] = lpContext->ptKey[j];
			ptBest1[i+1].x = (short)((lpContext->ptKey[j-1].x + lpContext->ptKey[j].x) / 2);
			ptBest1[i+1].y = (short)((lpContext->ptKey[j-1].y + lpContext->ptKey[j].y) / 2);
			for(j=i+1; j<=nMax; j++)
				ptBest1[j+1] = lpContext->ptKey[j];
			fError1 = getDistanceFromInitialPoint(ptBest1, nOut, &lpContext->rectMax);
			if (fError1 < fError)
			{
				memcpy(ptOut, ptBest1, sizeof(SPoint)*nOut);
				fError = fError1;
			}
		}
		// test case: '暮'10-th
		if (m_bEnableExhaust && fError>lpContext->m_fError+EPSILON)
		{
			fError1 = exhaustFind(ptBest1, nOut, lpContext);
			if (fError1>-EPSILON && fError1<fError)
			{
				memcpy(ptOut, ptBest1, sizeof(SPoint)*nOut);
				fError = fError1;
			}
		}
	}
	return fError;
}

float CParseStrokeKeyPoint::exhaustFind(SPoint *ptOut, int nOut, const SFindPointContext *lpContext) const
{
	float fError = (lpContext->ptKey!=NULL ? lpContext->m_fError : -1);
	RECT rectMax = lpContext->rectMax;
	// 9 points font is enough for all Chn strokes.
	int xMax = rectMax.right - rectMax.left + 1;
	int yMax = rectMax.bottom - rectMax.top + 1;
	int nXRatio = (int)(xMax / 12.0f + 0.5f);
	int nYRatio = (int)(yMax / 12.0f + 0.5f);
	nXRatio = max(nXRatio, 1);
	nYRatio = max(nYRatio, 1);
	if (nXRatio>1 || nYRatio>1)
	{
		CParseStrokeKeyPoint smallRectParser;
		SIZE size = {xMax / nXRatio, yMax / nYRatio};
		int i, nList = 0;
		SPoint *ptList = new SPoint[m_nPoint];
		float fRateX = 1.0f / nXRatio;
		float fRateY = 1.0f / nYRatio;
		for(i=0; i<m_nPoint; i++)
		{
			ptList[nList].x = (short)((m_lpPoint[i].x - rectMax.left) * fRateX + 0.5f);
			ptList[nList].y = (short)((m_lpPoint[i].y - rectMax.top) * fRateY + 0.5f);
			if (nList>0 && ptList[nList].x==ptList[nList-1].x && ptList[nList].y==ptList[nList-1].y)
				NULL;
			else
				nList++;
		}
		smallRectParser.setAllPoint(ptList, nList, &size);
		SPoint ptSmall[MAX_OUT];
		RECT rectSmall = {0, 0, size.cx, size.cy};
		smallRectParser.getMinimumDistance(ptSmall, nOut, &rectSmall, -1);
		delete[] ptList;
		// to restore into current space
		for(i=0; i<nOut; i++)
		{
			ptOut[i].x = (short)(ptSmall[i].x * nXRatio + rectMax.left);
			ptOut[i].y = (short)(ptSmall[i].y * nYRatio + rectMax.top);
		}
		fError = getDistanceFromInitialPoint(ptOut, nOut, &lpContext->rectMax);
	}
	else
	{
		fError = getMinimumDistance(ptOut, nOut, &lpContext->rectMax, fError);
	}
	return fError;
}

float CParseStrokeKeyPoint::getMinimumDistance(SPoint *ptBest, int nOut, const RECT *lpRect, float fMaxError) const
{
	CContourDistance contourDist(m_lpPoint, m_nPoint, DIST_DEFAULT);
	contourDist.m_bIncludeHeadTail = TRUE;
	// exhausted searching..., too slow to run
	SPoint *ptEnum;
	int nEnum = enumRectPoint(&ptEnum, lpRect);
	if (nOut >= nEnum || nOut >= MAX_OUT)
	{
		delete[] ptEnum;
		return MAX_FLOAT;	// unexpected error
	}
	SLargeIndex li;
	li.Init(nOut, nEnum);
	float f, fMinError = fMaxError;
	SPoint ptList[MAX_OUT];
	BOOL bContinue = TRUE;
	int nLast0 = -1;
	do{
		for(int m=0; m<nOut; m++)
			ptList[m] = ptEnum[li.m_nIndex[m]];
		if (fMinError > 0) {
			if (nLast0 != li.m_nIndex[0]) {
				SFPoint fP = {(float)ptList[0].x, (float)ptList[0].y};
				float f0 = CContourDistance::getDistanceSquare(&fP, m_lpPoint);
				if (f0 > fMinError * fMinError)
				{
					li.m_nIndex[0]++;
					if (li.m_nIndex[0] >= nEnum)
						bContinue = FALSE;
					else
						bContinue = li.selectIndex0();
					continue;
				}
				nLast0 = li.m_nIndex[0];
			}
		}
		f = contourDist.getDistance(ptList, nOut, fMinError);
		if (fMinError < 0 || f < fMinError)
		{
			memcpy(ptBest, ptList, sizeof(SPoint)*nOut);
			fMinError = f;
		}
		bContinue = li.updateIndex();
	}while(bContinue);
	delete[] ptEnum;
	return fMinError;
}

/** for intercept line data
 *
 * for shade area of two contour lines
 */
struct SCrossLineData
{
public:
	/// intercept point
	float	m_fXPos;
	/// -1: single dot on the above; 1: single dot under the line; 0, intercept line
	int		m_nType;
	/// index of current line
	int		m_nLineIndex;

public:
	/// callback for qsort/bsearch
	static int __cdecl compareX(const void *p, const void *q);
};
int SCrossLineData::compareX(const void *p, const void *q)
{
	const SCrossLineData *p1 = (const SCrossLineData *)p;
	const SCrossLineData *p2 = (const SCrossLineData *)q;
	if (p1->m_fXPos < p2->m_fXPos-EPSILON)
		return -1;
	if (p1->m_fXPos > p2->m_fXPos+EPSILON)
		return 1;
	if (p1->m_nType < 0 && p2->m_nType > 0)
		return -1;
	if (p1->m_nType > 0 && p2->m_nType < 0)
		return -1;
	return 0;
}

float CParseStrokeKeyPoint::getCurrentDistance(SPoint *ptBest, int nOut, const RECT *lpRect, float fMaxError) const
{
	float fError;
	ASSERT(nOut > 1);
	int nDist = getDistanceType();
	switch(nDist)
	{
	case 5:
		fError = getWeightParameterCurveDistance(ptBest, nOut, fMaxError);
		break;
	case 4:
		fError = getParameterCurveDistance(ptBest, nOut, fMaxError);
		break;
	case 3:
		fError = getContourShadeArea(ptBest, nOut, lpRect);
		break;
	case 2:
		{
			CContourDistance contourDist(m_lpPoint, m_nPoint, DIST_DEFAULT);
			contourDist.m_bIncludeHeadTail = TRUE;
			fError = contourDist.getDistance(ptBest, nOut, fMaxError);
		}
		break;
	case 1:
		{
			CContourDistance contourDist(m_lpPoint, m_nPoint, DIST_DEFAULT);
			// should include head-tail gap, test case: '饧'-4th
			contourDist.m_bIncludeHeadTail = FALSE;
			fError = contourDist.getDistance(ptBest, nOut, fMaxError);
		}
		break;
	default:
		fError = 0;
		break;
	}
	return fError;
}

float CParseStrokeKeyPoint::getDistanceFromInitialPoint(SPoint *ptBest, int nOut, const RECT *lpRect) const
{
	BOOL bUpdated;
	float fError, fCheck;
	fError = getCurrentDistance(ptBest, nOut, lpRect, -1);
	do{
		bUpdated = FALSE;
		// to enumerate all key-points
		for(int n=0; n<nOut; n++)
		{
			int m = -1;
			// to select a neighbour point which leads to the smallest distance
			SPoint ptSave = ptBest[n];
			for(int i=0; i<_countof(OFFSET_XY); i++)
			{
				SPoint pt0 = ptSave;
				if (!offsetPoint(&pt0, i, lpRect))
					continue;
				ptBest[n] = pt0;
				fCheck = getCurrentDistance(ptBest, nOut, lpRect, fError);
				ptBest[n] = ptSave;
				if (fCheck < fError-EPSILON) {
					fError = fCheck;
					m = i;
				}
			}
			// may not find any updates
			if (m >= 0) {
				offsetPoint(&ptBest[n], m, lpRect);
				bUpdated = TRUE;
			}
		}
	}while(bUpdated);
	return fError;
}

float CParseStrokeKeyPoint::getContourShadeArea(const SPoint *ptBest, int nOut, const RECT *lpRect) const
{
	int i, y, n, mType;
	// to create point list
	int nMaxLine = m_nPoint + nOut;
	SPoint *pt = new SPoint[nMaxLine + 1];
	for(i=0; i<m_nPoint; i++)
		pt[i] = m_lpPoint[i];
	for(i=0; i<nOut; i++)
		pt[m_nPoint + i] = ptBest[nOut - i - 1];
	pt[m_nPoint + nOut] = m_lpPoint[0];
	// to count area
	float x, fArea = 0;
	int xMin = lpRect->left - 1;
	int xMax = lpRect->right + 1;
	SCrossLineData *pCross = new SCrossLineData[nMaxLine];
	for(y=lpRect->top; y<=lpRect->bottom; y++)
	{
		int nCross = 0;
		for(i=0; i<nMaxLine; i++)
		{
			SPoint pt0 = pt[i];
			SPoint pt1 = pt[i+1];
			// to ignore trival case
			if (pt0.y == pt1.y ||	// a simple point, or horz. line
				(pt0.y < y && pt1.y < y) ||	// on the above
				(pt0.y > y && pt1.y > y))		// under the line
				continue;
			x = pt0.x + (y - pt0.y) * (pt1.x - pt0.x) / (float)(pt1.y - pt0.y);
			if (x <= xMin || x >= xMax)
				continue;	// rare case
			SCrossLineData cld;
			cld.m_fXPos = x;
			cld.m_nLineIndex = i;
			if (pt0.y < y)
				cld.m_nType = (pt1.y==y ? -1 : 0);
			else if(pt0.y > y)
				cld.m_nType = (pt1.y==y ? 1 : 0);
			else
				cld.m_nType = (pt1.y<y ? -1 : 1);
			pCross[nCross++] = cld;
		}
		if (nCross <= 1)
			continue;
		if (nCross > 2) {
			qsort(pCross, nCross, sizeof(SCrossLineData), SCrossLineData::compareX);
			mType = -100;
			x = 0;
			for(n=0; n<nCross; n++)
			{
				if (mType == pCross[n].m_nType)
				{
					mType = -100;
					continue;
				}
				if (mType > -100)
					fArea += max(pCross[n].m_fXPos - x, 0);
				mType = pCross[n].m_nType;
				x = pCross[n].m_fXPos;
				if (mType != 0)
					n++;
			}
		} else {
			fArea += fabsf(pCross[0].m_fXPos - pCross[1].m_fXPos);
		}
	}
	delete[] pCross;
	delete[] pt;
	return fArea;
}

///////////////////////////////////////////////////////////////////////////////

/** helper class to count points of parameter curve
 */
struct SParameterCurve
{
public:
	/** to create parameterized-curve
	 * @param lpPoint [in] some fixed SPoint
	 * @param nPoint count of lpPoint, should be larger than 1
	 */
	SParameterCurve(const SPoint *lpPoint, int nPoint);
	~SParameterCurve();

public:
	/// to query maximum length
	float getSumOfDist(void);
	/// to use cache
	BOOL enableCache(SFPoint *ptBuf, int nBuf);
	/// to set parameter T, creating middle points
	BOOL initMaximumParameter(int nMaxT);
	/// to query points by given 0-based index, in range [0, T]
	BOOL getPoint(SFPoint *lpPoint, int t) const;

protected:
	/// input curve points
	const SPoint	*m_lpPoint;
	/// count of m_lpPoint
	int		m_nPoint;
	/// distance of every line segment, count is m_nPoint-1
	float	*m_pfDist;
	/// sum of total length
	float	m_fSumDist;

protected:
	/// maximum count of parameter
	int		m_nMaxT;
	/// parameterized point list
	SFPoint	*m_ptBuf;

protected:
	SFPoint	*m_ptCache;
	int		m_nCache;

protected:
	SParameterCurve(const SParameterCurve&);
	SParameterCurve& operator=(const SParameterCurve&);
};

SParameterCurve::SParameterCurve(const SPoint *lpPoint, int nPoint)
{
	ASSERT(lpPoint!=NULL && nPoint>=2);
	m_lpPoint = lpPoint;
	m_nPoint = nPoint;
	m_pfDist = NULL;
	m_fSumDist = -1.0f;

	m_nMaxT = 0;
	m_ptBuf = NULL;
	m_ptCache = NULL;
	m_nCache = 0;
}

SParameterCurve::~SParameterCurve()
{
	if (m_pfDist != NULL)
	{
		delete[] m_pfDist;
		m_pfDist = NULL;
	}
	if (m_ptBuf != NULL)
	{
		if (m_ptBuf != m_ptCache)
			delete[] m_ptBuf;
		m_ptBuf = NULL;
	}
}

float SParameterCurve::getSumOfDist(void)
{
	ASSERT(this != NULL);
	if (m_pfDist != NULL)
		return m_fSumDist;
	if (m_nPoint <= 1)
		return 0.0f;
	if (m_pfDist == NULL)
		m_pfDist = new float[m_nPoint-1];
	int dx, dy;
	m_fSumDist = 0;
	for(int i=1; i<m_nPoint; i++)
	{
		dx = m_lpPoint[i].x - m_lpPoint[i-1].x;
		dy = m_lpPoint[i].y - m_lpPoint[i-1].y;
		m_pfDist[i-1] = sqrtf((float)dx * dx + dy * dy);
		m_fSumDist += m_pfDist[i-1];
	}
	return m_fSumDist;
}

BOOL SParameterCurve::enableCache(SFPoint *ptBuf, int nBuf)
{
	m_ptCache = ptBuf;
	m_nCache = (m_ptCache!=NULL ? nBuf : 0);
	return 0;
}

BOOL SParameterCurve::initMaximumParameter(int nMaxT)
{
	ASSERT(this != NULL);
	// to prepare, check arguments
	if (m_ptBuf != NULL)
	{
		if (m_ptBuf != m_ptCache)
			delete[] m_ptBuf;
		m_ptBuf = NULL;
	}
	if (!m_lpPoint || nMaxT < 1)
		return FALSE;
	// to ensure to be initialized, create index-0 point
	getSumOfDist();
	m_nMaxT = nMaxT;
	if (m_ptCache!=NULL && m_nMaxT+1<m_nCache)
		m_ptBuf = m_ptCache;
	else
		m_ptBuf = new SFPoint[m_nMaxT + 1];
	m_ptBuf[0].x = m_lpPoint[0].x;
	m_ptBuf[0].y = m_lpPoint[0].y;
	// to create all other points
	int nLastIdx = 0;
	float s, f, fNext;
	float fBase = m_fSumDist / m_nMaxT;
	float fCurDist = 0;
	SFPoint fP;
	for(int t=1; t<=m_nMaxT; t++)
	{
		f = t * fBase;
		fNext = fCurDist + m_pfDist[nLastIdx];
		while((fNext < f) && (nLastIdx+2 < m_nPoint)) {
			fCurDist = fNext;
			nLastIdx++;
			fNext = fCurDist + m_pfDist[nLastIdx];
		}
		if (t == m_nMaxT) {
			fP.x = m_lpPoint[m_nPoint-1].x;
			fP.y = m_lpPoint[m_nPoint-1].y;
		} else {
			s = (f - fCurDist) / max(m_pfDist[nLastIdx], 1.0f);
			fP.x = m_lpPoint[nLastIdx].x + (m_lpPoint[nLastIdx+1].x - m_lpPoint[nLastIdx].x) * s;
			fP.y = m_lpPoint[nLastIdx].y + (m_lpPoint[nLastIdx+1].y - m_lpPoint[nLastIdx].y) * s;
		}
		m_ptBuf[t] = fP;
	}
	return TRUE;
}

BOOL SParameterCurve::getPoint(SFPoint *lpPoint, int t) const
{
	if (!m_ptBuf || !lpPoint || t<0 || t>m_nMaxT)
		return FALSE;
	*lpPoint = m_ptBuf[t];
	return TRUE;
}

///////////////////////////////////////////////////////////////////////////////

float CParseStrokeKeyPoint::getParameterCurveDistance(const SPoint *ptBest, int nOut, float fMaxError) const
{
	// to count length of source curve
	SParameterCurve pcCurr(m_lpPoint, m_nPoint);
	float fSumDist1 = pcCurr.getSumOfDist();
	int nMax1 = (int)(fSumDist1 + 0.5f);
	// to count length of simulated curve
	SParameterCurve pcBest(ptBest, nOut);
	float fSumDist2 = pcBest.getSumOfDist();
	int nMax2 = (int)(fSumDist2 + 0.5f);
	// to count their distance(sum of square, then, square root)
	int tMax = max(nMax1, nMax2);
	float fSum2 = 0.0f;
	SFPoint fP1, fP2;
	int nMaxCache = (m_maxSize.cx + m_maxSize.cy + 1) * 5;
	pcCurr.enableCache(m_ptCache, nMaxCache);
	pcCurr.initMaximumParameter(tMax);
	if (m_ptCache != NULL)
		pcBest.enableCache(m_ptCache + nMaxCache, nMaxCache);
	pcBest.initMaximumParameter(tMax);
	float fCheck = (fMaxError>0 ? fMaxError*fMaxError : -1);
	for(int t=0; t<=tMax; t++)
	{
		pcCurr.getPoint(&fP1, t);
		pcBest.getPoint(&fP2, t);
		fSum2 += (fP1.x - fP2.x) * (fP1.x - fP2.x) + (fP1.y - fP2.y) * (fP1.y - fP2.y);
		if (fCheck>0 && fSum2>fCheck)
			return fMaxError+100;
	}
	return sqrtf(fSum2);
}

float CParseStrokeKeyPoint::getWeightParameterCurveDistance(const SPoint *ptBest, int nOut, float fMaxError) const
{
	// to count length of source curve
	SParameterCurve pcCurr(m_lpPoint, m_nPoint);
	float fSumDist1 = pcCurr.getSumOfDist();
	int nMax1 = (int)(fSumDist1 + 0.5f);
	// to count length of simulated curve
	SParameterCurve pcBest(ptBest, nOut);
	float fSumDist2 = pcBest.getSumOfDist();
	int nMax2 = (int)(fSumDist2 + 0.5f);
	// to count their distance(sum of square, then, square root)
	int tMax = max(nMax1, nMax2);
	SFPoint fP1, fP2;
	int nMaxCache = (m_maxSize.cx + m_maxSize.cy + 1) * 5;
	pcCurr.enableCache(m_ptCache, nMaxCache);
	pcCurr.initMaximumParameter(tMax);
	if (m_ptCache != NULL)
		pcBest.enableCache(m_ptCache + nMaxCache, nMaxCache);
	pcBest.initMaximumParameter(tMax);
	float fCheck = (fMaxError>0 ? fMaxError*fMaxError : -1);

	float fSum2 = 0.0f;
	pcCurr.getPoint(&fP1, 0);
	pcBest.getPoint(&fP2, 0);
	fSum2 += (fP1.x - fP2.x) * (fP1.x - fP2.x) + (fP1.y - fP2.y) * (fP1.y - fP2.y);
	if (fCheck>0 && fSum2>fCheck)
		return fMaxError+100;

	pcCurr.getPoint(&fP1, tMax);
	pcBest.getPoint(&fP2, tMax);
	float fDist2 = (fP1.x - fP2.x) * (fP1.x - fP2.x) + (fP1.y - fP2.y) * (fP1.y - fP2.y);
	fSum2 += 3 * fDist2;
	if (fCheck>0 && fSum2>fCheck)
		return fMaxError+100;

	for(int t=1; t<tMax; t++)
	{
		pcCurr.getPoint(&fP1, t);
		pcBest.getPoint(&fP2, t);
		fSum2 += (fP1.x - fP2.x) * (fP1.x - fP2.x) + (fP1.y - fP2.y) * (fP1.y - fP2.y);
		if (fCheck>0 && fSum2>fCheck)
			return fMaxError+100;
	}
	return sqrtf(fSum2);
}

float CParseStrokeKeyPoint::findCentralPoint(SPoint *lpOut, const RECT *lpRect) const
{
	ASSERT(m_lpPoint != NULL && m_nPoint > 0);

	int nSumX = 0;
	int nSumY = 0;
	for(int i=0; i<m_nPoint; i++)
	{
		nSumX += m_lpPoint[i].x;
		nSumY += m_lpPoint[i].y;
	}
	SPoint ptBest = {(short)(nSumX/m_nPoint), (short)(nSumY/m_nPoint)};
	CContourDistance contourDist(m_lpPoint, m_nPoint, DIST_DEFAULT);
	float fMinError;
	int nDist = getDistanceType();
	switch(nDist)
	{
	default:	// 1 & 4
		contourDist.m_bIncludeHeadTail = FALSE;
		fMinError = contourDist.getDistance(&ptBest, 1, -1);
		break;
	case 3:
		fMinError = getContourShadeArea(&ptBest, 1, lpRect);
		break;
	case 5:
	case 6:
		contourDist.m_bIncludeHeadTail = FALSE;
		fMinError = contourDist.getDistance(&ptBest, 1, -1);
		if (m_nPoint > 0)
		{
			SPoint ptEnd = m_lpPoint[m_nPoint-1];
			float fSum2 = powf((float)ptEnd.x-ptBest.x, 2.0f) + powf((float)ptEnd.y-ptBest.y, 2.0f);
			fMinError = sqrtf(fMinError * fMinError + 2 * fSum2);
		}
		break;
	case 2:
		contourDist.m_bIncludeHeadTail = TRUE;
		fMinError = contourDist.getDistance(&ptBest, 1, -1);
		break;
	}
	// to update locally
	float f, fError = fMinError;
	BOOL bUpdated;
	do{
		bUpdated = FALSE;
		for(int i=0; i<_countof(OFFSET_XY); i++)
		{
			SPoint pt0 = ptBest;
			if (!offsetPoint(&pt0, i, lpRect))
				continue;
			switch(nDist)
			{
			case 6:
			case 5:
				f = contourDist.getDistance(&ptBest, 1, -1);
				if (m_nPoint > 0)
				{
					SPoint ptEnd = m_lpPoint[m_nPoint-1];
					float fSum2 = powf((float)ptEnd.x-ptBest.x, 2.0f) + powf((float)ptEnd.y-ptBest.y, 2.0f);
					f = sqrtf(f * f + 2 * fSum2);
				}
				break;
			case 3:
				f = getContourShadeArea(&pt0, 1, lpRect);
				break;
			default:	// same with 1 & 2 & 4
				f = contourDist.getDistance(&pt0, 1, fError);
				break;
			}
			if (f < fError - EPSILON)
			{
				ptBest = pt0;
				bUpdated = TRUE;
				fError = f;
			}
		}
	}while(bUpdated);
	*lpOut = ptBest;
	return fError;
}
